//
//  Problem6.swift
//  LeetCode 6 Z 字形变换
//
//  Created by 毕武侠 on 2020/7/27.
//  Copyright © 2020 毕武侠. All rights reserved.
//

import UIKit

/*
 将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。

 比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：

 L   C   I   R
 E T O E S I I G
 E   D   H   N
 之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。

 请你实现这个将字符串进行指定行数变换的函数：

 string convert(string s, int numRows);
 示例 1:

 输入: s = "LEETCODEISHIRING", numRows = 3
 输出: "LCIRETOESIIGEDHN"
 示例 2:

 输入: s = "LEETCODEISHIRING", numRows = 4
 输出: "LDREOEIIECIHNTSG"
 解释:

 L     D     R
 E   O E   I I
 E C   I H   N
 T     S     G

 */
class Problem6: NSObject {
    func test() {
        print(convert("LEETCODEISHIRING", 3))
        print(convert("LEETCODEISHIRING", 4))
    }
    
    /*
     方式一： 使用多维数据的方式
     */
    func convert(_ s: String, _ numRows: Int) -> String {
        if s.count <= 2 || numRows <= 1 {
            return s
        }
        
        if s.count <= numRows {
            return s
        }
        
        var lists:[[String.Element]] = []
        for _ in 0..<numRows {
            lists.append([])
        }
        
        var i: Int = 0
        var flag: Int = -1
        for char in s {
            lists[i].append(char)
            if i == 0 || i == numRows - 1 {
                flag = -flag
            }
            i += flag
        }
        
        var str: String = ""
        for list in lists {
            for char in list {
                str.append(char)
            }
        }
        
        return str
    }
    
    /*
     方式二：使用数学技巧
     "LEETCODEISHIRING" 行数为 3，排列如下：
     
     L   C   I   R                  0   4   8     12    16      i * (line + 1)   i * (4)
     E T O E S I I G                1 3 5 7 9  11 13 15 17      i * (line - 1) + 1
     E   D   H   N                  2   6   10    14    18      i * (line + 1) + 2
     
     "LEETCODEISHIRING" 行数为 4，排列如下：

     L     D     R                  0     6       12            i * (line + 2)   i * (6)
     E   O E   I I                  1   5 7    11 13            i * (line + 2)
     E C   I H   N                  2 4   8 10    14
     T     S     G                  3     9       15

     第一行规律： i * (line + line - 2)
     第二行规律：
     if (i % 2 == 1) {
        1 + line
     }
     */
    
}
